package LeetCode.test;

/**
 * @Description: 三向字符串快速排序
 * @Date: 2023/5/1 11:09
 * @Author: SALENZ
 * @Version: 1.0
 */
public class Quick3string{
    //三向字符串快速排序
    private static int charAt(String s, int d) {
        if(d < s.length()) {
            return s.charAt(d);
        }
        return -1;
    }

    public static void sort(String[] a) {
        sort(a, 0, a.length - 1, 0);
    }

    private static void sort(String[] a, int lo, int hi, int d) {
        if(hi <= lo) {
            return;
        }
        int lt = lo, gt = hi, i = lo + 1;
        int v = charAt(a[lo], d);
        while(i <= gt) {
            int t = charAt(a[i], d);
            if(t < v) {
                exch(a, lt++, i++);
            }else if(t > v) {
                exch(a, i, gt--);
            }else {
                i++;
            }
        }
        //a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]
        sort(a, lo, lt - 1, d);
        if(v >= 0) {
            sort(a, lt, gt, d + 1);
        }
        sort(a, gt + 1, hi, d);
    }

    private static void exch(String[] a, int i, int j) {
        String t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

